/*
2021-7-19
https://leetcode-cn.com/problems/maximum-number-of-points-with-cost/
*/
class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        int n=points.size();
        int m=points[0].size();
        long dp[100005];
        memset(dp,0,sizeof dp);
        for(int i=0;i<n;i++)
        {
            long cur[100005];
            long lmax=0;
            for(int j=0;j<m;j++)
            {
                lmax=max(lmax-1,dp[j]);
                cur[j]=lmax;
            }
            long rmax=0;
            for(int j=m-1;j>=0;j--)
            {
                rmax=max(rmax-1,dp[j]);
                cur[j]=max(cur[j],rmax);
            }
            for(int j=0;j<m;j++)
                dp[j]=cur[j]+points[i][j];
        }
        long res=0;
        for(int i=0;i<m;i++)
            res=max(res,dp[i]);
        return res;
    }
};
